package org.jmpo;

/**
 * Множество целых чисел (int) в промежутке [MIN, MAX] включая концы.
 * Хранит данные компактным образом в массиве битов. 
 * Каждое число может хранится в множестве в единственном экземпляре.
 */
public class CompactSet {
    /**
     * Создаёт новое пустое компактное множество
     * @param min  минимальное число, которое можно хранить в множестве
     * @param max  максимльное число, которое можно хранить в множестве
     */
    public CompactSet(int min, int max) {
        this.MIN  = min;
        this.MAX  = max;
        this.size = max - min + 1;
        this.data = new int[size/32 + 1];
    }

    /**
     * Проверяет наличие элемента в множестве
     * @param i проверяемый элемент
     * @return  true - элемент присутствует, false - элемент отсутствует 
     */
    public boolean contains(int i) {
        if (i > MAX || i < MIN) return false;
        var pos = i - MIN;
        return (data[pos/32] & (1 << pos % 32)) > 0;
    }

    /**
     * Удаляет элемент из множества
     * @param i удаляемый элемент
     * @return  true - еслии элемент содержался и был успешно удалён, false - элемент не содержался
     */
    public boolean remove(int i) {
        if (i > MAX || i < MIN) return false;
        var pos = i - MIN;
        if (!((data[pos/32] & (1 << pos % 32)) > 0)) return false;
        data[pos/32] &= ~(1 << pos % 32);
        return true;
    }

    /**
     * Гарантирует присутствие элемента в множестве.
     * Т.е. выполняется аксиома:
     * var addRes = set.add(k);
     * var cntRes = set.contains(k);
     * assertTrue(addRes == cntRes); 
     * @param i добавляемый элемент
     * @return  true - если элемент успешно добавлен, иначе - false
     */
    public boolean ensure(int i) {
        if (i > MAX || i < MIN) return false;
        var pos = i - MIN;
        data[pos/32] |= (1 << pos % 32);
        return true;
    }

    private final int[] data;
    private final int size;
    private final int MIN, MAX;
}
